/**
 * FileName: BreadthFirstSearch
 * Author:   powersi
 * Date:     2021/1/13 7:45
 * Description: bfs
 */
package com.zm.demo.core.leetcode.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Description: bfs
 * Author:      powersi
 * Date:        2021/1/13 7:45
 */
public class BreadthFirstSearch {


    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.buildGraph();

        bfs(8, 1, graph.getAdj());
    }

    public static void bfs(int s, int t, LinkedList<Integer>[] adj){
        if (s == t) return;
        boolean visited[] = new boolean[adj.length];
        //默认第一个为已访问。
        visited[s] = true;

        //初始化边数组，默认为没有，以 -1 为退出条件
        int prev[] = new int[adj.length];
        for (int i = 0; i < prev.length; i++) {
            prev[i] = -1;
        }

        //借助队列来实现，将第一个顶点加入队列
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);

        while (queue.size()>0){
            //拿队列头里面的顶点，搜索这个顶点连接的所有顶点，
            int w = queue.poll();
            for (int i = 0; i < adj[w].size(); i++) {
                int q = adj[w].get(i);
                //如果没有访问过，进行访问。否则，跳过当前顶点。
                if (!visited[q]){
                    prev[q] = w;//记录边，当前顶点为坐标，上一个顶点为值

                    //如果当前顶点为目标顶点，则进行打印，结束搜索。
                    if (q == t){
                        print(prev, s, t);
                        return;
                    }

                    //标记当前顶点为已访问
                    visited[q]=true;
                    //将当前顶点加入队列，用于寻找当前顶点的下一层
                    queue.add(q);
                }
            }
        }
    }

    public static void print(int []prev, int s, int t){

        if (s != t && prev[t] != -1){
            print(prev, s, prev[t]);
        }
        System.out.println(t + " ");
    }
}
